package com.lyj.sc.SecondBruchToReview.String20220722;

/**
 * @program: code-random
 * @description: 字符串
 * @author: lyj
 * @create: 2022-07-22 15:36
 * @version: 1.0
 * @Modifier By:
 **/
public class Solution {
    // 344.反转字符串
    public void reverseString(char[] s) {
        //字符串
        int slow = 0;
        int fast = s.length-1;
        while (slow<fast){
            char temp = s[slow];
            s[slow]=s[fast];
            s[fast]=temp;
            slow++;
            fast--;
        }
    }
    // 541. 反转字符串II
    public String reverseStr(String s, int k) {
        StringBuilder res = new StringBuilder();
        int start = 0;
        int end = s.length();
        while (start<end){
            StringBuilder builder = new StringBuilder();
            int firstK = start+k > end? end:start+k;
            int secondK = start+2*k >end?end:start+2*k;

            builder.append(s.substring(start, firstK));
            res.append(builder.reverse());

            if(firstK<secondK){
                res.append(s.substring(firstK,secondK));
            }
            start+=2*k;
        }
        return res.toString();
    }

    //剑指Offer 05.替换空格
    public String replaceSpace(String s) {
        if(s==null || s.length()==0){
            return s;
        }
        StringBuffer str = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)==' '){
                str.append("  ");
            }
        }
        int len = s.length()-1;
        s+=str.toString();
        //双指针
        char[] chars = s.toCharArray();
        for(int j=s.length()-1,i=len;i>=0;i--,j--){
            if (chars[i]!=' '){
                chars[j]=chars[i];
            }else {
                chars[j--]='0';
                chars[j--]='2';
                chars[j]='%';
            }
        }
        return new String(chars);
    }
    //151. 颠倒字符串中的单词
    public String reverseWords(String s) {
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverse(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }
    //需要三个函数
    //1.清除两边的空格和中间的空格
    public StringBuilder removeSpace(String s){
        int index = 0;
        int end = s.length()-1;
        while (s.charAt(index)==' ') {
            index++;
        }
        while (s.charAt(end)==' ') {
            end--;
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)==' ' && s.charAt(i-1)==' '){
                continue;
            }
            res.append(s.charAt(i));
        }
        return res;
    }
    //2.反转单词
    public void reverse(StringBuilder s,int a,int b){
        while (a<b){
            char c = s.charAt(a);
            s.setCharAt(a,s.charAt(b));
            s.setCharAt(b,c);
            a++;
            b--;
        }
    }
    public void reverseEachWord(StringBuilder sb){
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverse(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }

    //剑指 Offer 58 - II. 左旋转字符串
    public String reverseLeftWords(String s, int n) {
        int len = s.length();
        StringBuilder res = new StringBuilder(s);
        reverse(res,0,n-1);
        reverse(res,n,len-1);
        return res.reverse().toString();
    }

    public void reverseString(StringBuilder sb , int start ,int end){
        while (start<end){
            char temp = sb.charAt(start);
            sb.setCharAt(start,sb.charAt(end));
            sb.setCharAt(end,temp);
            start++;
            end--;
        }
    }
    // 28. 实现 strStr()
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }
        int[] next = new int[needle.length()];
        getNext(next,needle);
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (i>0 && haystack.charAt(i)!=needle.charAt(j)){
                j=next[j-1];
            }
            if (haystack.charAt(i)==needle.charAt(j)){
                j++;
            }
            if(j==needle.length()){
                return i-needle.length()+1;
            }
        }
        return -1;
    }
    // 28.获得next数组
    public  void getNext(int[]next,String needle){
        int j=0;
        next[0]=0;
        for (int i = 1; i < next.length; i++) {
            while (j>0 && needle.charAt(i)!=needle.charAt(j)){
                j=next[j-1];
            }
            if (needle.charAt(i)==needle.charAt(j)){
                j++;
            }
            next[i]=j;
        }
    }
    // 459.重复的子字符串
    public boolean repeatedSubstringPattern(String s) {
        if(s.length()==0){
            return true;
        }
        int[] next = new int[s.length()];
        getNext1(next,s);
        // next[s.length()-1]>0
        if((s.length()%(s.length()-next[s.length()-1]))==0 && next[s.length()-1]>0){
            return true;
        }
        return false;
    }
    public void getNext1(int[] next,String needle){
        int j=0;
        next[0]=0;
        for (int i = 1; i < next.length; i++) {
            while (j>0 && needle.charAt(i)!=needle.charAt(j)){
                j=next[j-1];
            }
            if (needle.charAt(i)==needle.charAt(j)){
                j++;
            }
            next[i]=j;
        }
    }
}

